package leetcode_day._2022._202201._1120;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/1/11 9:15
 * 逃离迷宫
 * 在一个足够大的空间里，有少数障碍物，问两点是否能够连通
 * 算法：广度优先搜索
 * 当两点相隔较远时，BFS 可能会搜完整个棋盘，会超时
 * 从 source 开始跑一遍 BFS，然后从 target 开始跑一遍 BFS，
 * 同时设置一个最大的访问点数 MAX，若从两者出发能够访问的点数都大于 MAX，那么两点肯定连通
 */
public class _11_1036 {

    static int EDGE = (int) 1e6, MAX = 0;
    // 用来将格子的坐标转化成一个唯一的整数，方便比较
    static long BASE = 131L;
    Set<Long> block = new HashSet<>();
    int[][] dirs = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        for (int[] b : blocked) block.add(b[0] * BASE + b[1]);
        int n = blocked.length;
        MAX = n * (n - 1) / 2;
        return check(source, target) && check(target, source);
    }
    boolean check(int[] a, int[] b) {
        Set<Long> vis = new HashSet<>();
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(a);
        vis.add(a[0] * BASE + a[1]);
        while (!queue.isEmpty() && vis.size() <= MAX) {
            int[] poll = queue.pollFirst();
            int x = poll[0], y = poll[1];
            if (x == b[0] && y == b[1]) return true;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= EDGE || ny < 0 || ny >= EDGE) continue;
                long hash = nx * BASE + ny;
                if (block.contains(hash)) continue;
                if (vis.contains(hash)) continue;
                queue.addLast(new int[]{nx, ny});
                vis.add(hash);
            }
        }
        return vis.size() > MAX;
    }

}
